/*                         Ralph Chess

		   move.cpp is a part of rchess

		 rchess is a very simple chess engine 

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with rchess.  If not, see <http://www.gnu.org/licenses/>.

                   Copyright 2013 Ralph Glass                                              


         move.cpp - board representation, search, evaluation
*/

#include <iostream>
#include <sstream>
#include <algorithm>
#include <stdexcept>
#include <array>
#include "debug.h"
#include "time.h"
#include "evaluation.h"

enum Pieces  { pawn = 'p', knight = 'n', rook = 'r', bishop = 'b', queen = 'q', king = 'k' };

struct piece { char type; int x; int y; int pos; int value;};
struct move  { int x; int y; };
struct scored_move { int score; piece p; move m; };
struct status { bool white; move en_passant; } status;
struct castling { 
	bool already_castled;
	bool king_moved; 
	bool short_rook_moved; 
	bool rook_queenside_moved;
} computer_castling { false, false, false, false };

const int white_pawn_starting_rank = 1;
const int black_pawn_starting_rank = 7;

std::array<struct piece, 64> chessboard, empty_board, table[64];
std::array<std::vector<std::vector<int> >, 64> rook_board;
std::array<std::vector<std::vector<int> >, 64> queen_board;
std::array<std::vector<std::vector<int> >, 64> bishop_board;
std::array<std::vector<int> , 64> knight_board;
std::array<std::vector<int> , 64> king_board;
std::array<int, 256> piece_value;
std::vector<piece> active_pieces;

const std::vector<move> all_knight_moves = {
	{ { 1, 2},{ 1,-2},{ 2, 1},{ 2,-1},  
	  {-1, 2},{-1,-2},{-2, 1},{-2,-1}  }};

const std::vector<move> all_pawn_moves = {
	{ { 0,-1},{ 0,-2} }};

const std::vector<move> all_pawn_attacks = {
	{ {-1,-1},{ 1,-1} }};

const std::vector<move> inverse_pawn_moves = {
	{ { 0, 1},{ 0, 2} }};

const std::vector<move> inverse_pawn_attacks = {
	{ {-1, 1},{ 1, 1} }};

const std::vector<move> all_rook_directions = {
	{ { 0,-1},{ 0, 1},{ 1, 0},{-1, 0} }};

const std::vector<move> all_bishop_directions = {
	{ {-1,-1},{-1, 1},{ 1, 1},{ 1,-1} }};

const std::vector<move> all_queen_directions = {
	{ { 0,-1},{ 0, 1},{ 1, 0},{-1, 0},
	  {-1,-1},{-1, 1},{ 1, 1},{ 1,-1} }};

const std::vector<move> all_king_moves = {
	{ { 0,-1},{ 0, 1},{ 1, 0},{-1, 0},
	  {-1,-1},{-1, 1},{ 1, 1},{ 1,-1} }};

int pos(int x, int y) {
	if (x < 0 or y < 0) throw std::runtime_error("negative x y error");
	return (x + ((8-y) * 8));}

int pos(move m ) {return pos(m.x, m.y);}

void out_of_bounds_check(int i) {
	if ( i < 0 or i > 63) throw std::runtime_error("out of bounds error");}

move to_move(int i) {
	out_of_bounds_check(i);
	return { i % 8, 8-(i/8) };}

void show_board(std::string board) {
	std::cout << std::endl;
	for (int i = 0; i < 8; i++) {
	for (int j = 0; j < 8; j++) {
		std::cout << board[(i*8)+j] << " ";} 
	std::cout << std::endl;}
	std::cout << std::endl;}

bool on_board(int x,int y) {return ( x > -1 and x < 8 and y > 0 and y < 9);}
bool on_board(move m)      {return ( m.x > -1 and m.x < 8 and m.y > 0 and m.y < 9);}
	
move new_square(piece p, move m) {return { p.x + m.x, p.y + m.y};}
move new_square(move m, move t)  {return { m.x + t.x, m.y + t.y};}

bool not_friendly(int pos) {
	if (status.white) {return (chessboard.at(pos).value <= 0);}
	else {return (chessboard.at(pos).value >= 0);}}

bool friendly(int i) {
	if (status.white) {return (chessboard.at(i).value > 0);}
	else {return (chessboard.at(i).value < 0);}}

bool enemy(int pos) {
	if (status.white) {return (chessboard.at(pos).value < 0);}
	else {return (chessboard.at(pos).value > 0);}}

bool en_passant(move m) {
	return (m.x == status.en_passant.x and m.y == status.en_passant.y); }

std::vector<int> ray_build(piece p , move direction) {
	std::vector<int> result;
	move target = {p.x,p.y};
	while(on_board(target.x,target.y)) {
		target = new_square(target, direction);
		if (on_board(target))
			result.push_back(pos(target));
		else return result;}
        return result;}

std::vector<int> legal_moves(piece p) {
	std::vector<int> result;
	move target;
        move passant;
	if (not ( std::islower(p.type) or std::isupper(p.type))) {
		throw std::runtime_error ("wrong piece type error");}
	if (status.white) p.type = std::tolower(p.type);
	if ( p.type == king) {
		for (auto el : king_board.at(p.pos))
			if (not_friendly(el)) { result.push_back(el);}}
	else if ( p.type == knight ) {
		for (auto el : knight_board.at(p.pos))
			if (not_friendly(el)) {result.push_back(el);}}
	else if ( p.type == pawn) {
		if (status.white) {
			if (p.y == white_pawn_starting_rank) {
				target  = new_square(p, inverse_pawn_moves[1]);
				passant = new_square(p, inverse_pawn_moves[0]);
				if (chessboard.at(pos(target )).type == '.' and
				    chessboard.at(pos(passant)).type == '.') {
					result.push_back(pos(target));}}

			target = new_square(p, inverse_pawn_moves[0]);
			if (on_board(target) and chessboard.at(pos(target)).type == '.'){
				result.push_back(pos(target));}
			for (auto m : inverse_pawn_attacks){
				target = new_square(p, m); 
				if (on_board(target) and 
				    (enemy(pos(target)) or en_passant(target))) {
					result.push_back(pos(target));}}}
		else {
			if (p.y == black_pawn_starting_rank) {
				target  = new_square(p, all_pawn_moves[1]);
				passant = new_square(p, all_pawn_moves[0]);
				if (chessboard.at(pos(target )).type == '.' and
				    chessboard.at(pos(passant)).type == '.') {
					result.push_back(pos(target));}}
			target = new_square(p, all_pawn_moves[0]);
			if (on_board(target) and chessboard.at(pos(target)).type == '.') {
					result.push_back(pos(target));};
			for (auto m : all_pawn_attacks) {
				target = new_square(p, m);
				if (on_board(target) and enemy(pos(target))) {
					result.push_back(pos(target));}}}}
	else if (p.type == bishop) {
		for (auto ray : bishop_board.at(p.pos)) {
			for (auto el : ray) {
				if (friendly(el)) {break;}
				else if (enemy(el)) {
					result.push_back(el);
					break;}
				else {
					result.push_back(el);}}}}
	else if (p.type == rook) {
		for (auto ray : rook_board.at(p.pos)) {
			for (auto el : ray) {
				if (friendly(el)) {break;}
				else if (enemy(el)) {
					result.push_back(el);
					break;} 
				else {
					result.push_back(el);}}}}
	else if (p.type == queen) {
		for (auto ray : queen_board.at(p.pos)) {
				for (auto el : ray) {
					if (friendly(el)) {break;}
					else if (enemy(el)) {
						result.push_back(el);
						break;} 
					else { 
						result.push_back(el);}}}}
	return result;}

bool check_from (piece p) {  
	move target;
	char isKing = 'K';
	if (status.white) isKing = 'k';
	if (status.white) p.type = std::tolower(p.type);
	if ( p.type == king) {
		for (auto el : king_board.at(p.pos))
			if (chessboard.at(el).type == isKing ) { return true;}}
	else if ( p.type == knight ) {
		for (auto el : knight_board.at(p.pos))
			if (chessboard.at(el).type == isKing) {return true;}}
	else if ( p.type == pawn) {
		if (status.white) {
			for (auto m : inverse_pawn_attacks){
				target = new_square(p, m); 
				if (on_board(target) and chessboard.at(pos(target)).type == isKing){
					return true;}}}
		else {
			for (auto m : all_pawn_attacks) {
				target = new_square(p, m);
				if (on_board(target) and chessboard.at(pos(target)).type == isKing) {
					return true;}}}}
	else if (p.type == bishop) {
		for (auto ray : bishop_board.at(p.pos)) {
			for (auto el : ray) {
				if (friendly(el)) {break;}
				else if (enemy(el)) {
					if ( chessboard.at(el).type == isKing) {return true;}
					break; } }}}
	else if (p.type == rook) {
		for (auto ray : rook_board.at(p.pos)) {
			for (auto el : ray) {
				if (friendly(el)) {break;}
				else if (enemy(el)) {
					if ( chessboard.at(el).type == isKing) {return true;}
					break; } }}}
	else if (p.type == queen) {
		for (auto ray : queen_board.at(p.pos)) {
			for (auto el : ray) {
				if (friendly(el)) {break;}
				else if (enemy(el)) {
					if ( chessboard.at(el).type == isKing) { return true;}
					break; } }}}
	return false;}
		
int random(short i) { 
	std::random_device random_gen;
	std::uniform_int_distribution <int> distribution(0,i-1);
	return distribution(random_gen);}

void bookkeeper(){
	int black_king = 4;
	int black_rook_kingside = 7;
	int black_rook_queenside = 0;
	if (chessboard.at(black_king).type != 'k') {
		computer_castling.king_moved = true;}
	if (chessboard.at(black_rook_kingside).type != 'r') {
		computer_castling.short_rook_moved = true;}
	if (chessboard.at(black_rook_queenside).type != 'r') {
		computer_castling.rook_queenside_moved = true;}}
	
bool castling_possible() {
	bool result;
	bool castling_avail;
	result = not (computer_castling.king_moved or computer_castling.short_rook_moved);
	castling_avail = (result and chessboard.at(5).type == '.' and chessboard.at(6).type == '.');
	return castling_avail;}

bool castling_queenside_possible() {
	bool legal;
	bool castling_available;
	legal = not (computer_castling.king_moved or computer_castling.rook_queenside_moved);
	castling_available = (legal and chessboard.at(1).type == '.' and
			     chessboard.at(2).type == '.' and chessboard.at(3).type == '.') ;
	return castling_available;}

void update_piece_list() {
	active_pieces.clear();
	if (status.white) {
		for (int i = 0 ; i < 64; i++)
			if (chessboard.at(i).value > 0) {
       				active_pieces.push_back(chessboard.at(i));}}
	else {
		for (int i = 0 ; i < 64; i++)
			if (chessboard.at(i).value < 0) {
				active_pieces.push_back(chessboard.at(i));}}}

void init_chessboard() {
	piece p;
	std::stringstream stream;
        stream	<< "rnbqkbnr"
		<< "pppppppp"
		<< "........"
		<< "........"
		<< "........"
		<< "........"
		<< "PPPPPPPP"
		<< "RNBQKBNR"; 
	std::string board = stream.str();
	for (int i = 0; i < 64; i++) {
		p.type = board.at(i);
		p.x    = i % 8;
		p.y    = 8 - (i / 8);
		p.pos  = i;
		p.value = piece_value[p.type];
		chessboard.at(i) = p;
		empty_board.at(i) = {'.', p.x, p.y, p.pos, 0};
		std::vector<int> moves;
		move target;
		for (auto m : all_knight_moves) {
			target = {p.x+m.x,p.y+m.y};
			if (on_board(target)) {
				moves.push_back(pos(target));}}
		knight_board.at(p.pos) = moves;
		moves.clear();
		for (auto m : all_king_moves) {
			target = {p.x+m.x,p.y+m.y};
			if (on_board(target)) {
				moves.push_back(pos(target));}}
		king_board.at(p.pos) = moves;
		std::vector<std::vector<int> > rays;
		std::vector<std::vector<int> > queen_rays;
		std::vector<int> ray;
		for (auto direction : all_rook_directions) {
			ray.clear();
			for (auto el : ray_build(p, direction)){
				ray.push_back(el);}
			rays.push_back(ray);
		        queen_rays.push_back(ray);}
		rook_board.at(p.pos) = rays;
		rays.clear();
		for (auto direction : all_bishop_directions) {
			ray.clear();
			for (auto el : ray_build(p, direction)){
				ray.push_back(el);}
			rays.push_back(ray);
		        queen_rays.push_back(ray);}
		bishop_board.at(p.pos) = rays;
                queen_board.at(p.pos) = queen_rays; }}

piece make_move(piece p, int new_pos) {
	piece store;
	int old_pos = p.pos;
	store = chessboard.at(new_pos);
	chessboard.at(old_pos) = empty_board.at(old_pos);
	p.x = empty_board.at(new_pos).x;
	p.y = empty_board.at(new_pos).y;
	p.pos = new_pos;
	chessboard.at(new_pos) = p;
	return store;}

void undo_move(piece p, piece target) {
	chessboard.at(target.pos) = target;
	chessboard.at(p.pos)      = p;}

void parse_usermove(std::string m) {
	piece p;
	unsigned int promoted = 5;
	piece r;
	std::string castling_white_kingside  = "e1g1";
	std::string castling_white_queenside = "e1c1";
	status.en_passant = {-1,-1};
	int x0 = m.at(0) - 'a';
	int y0 = m.at(1) - '0';
	int x1 = m.at(2) - 'a';
	int y1 = m.at(3) - '0';
	int old_pos = pos(x0,y0);
	int new_pos = pos(x1,y1);
	p = chessboard.at(old_pos);
	if (p.type == pawn and y0 == 2 and y1 == 4) {
		status.en_passant = {x0, y0 + 1};
	}
	if (m.length() == promoted){
		p.type = std::toupper(m.at(4));
		p.value = piece_value[p.type];}
	make_move(p, new_pos);
	if (m == castling_white_kingside) {
		r = chessboard.at(63);
		make_move(r, r.pos-2);}
	if (m == castling_white_queenside) {
		r = chessboard.at(56);
		make_move(r, r.pos+3);}
	update_piece_list();}

void make_castling_move() {
	piece k, r;
	k = chessboard.at(4);
	r = chessboard.at(7);
	make_move(k,k.pos+2);
	make_move(r,r.pos-2);}

void make_castling_queenside_move() {
	piece k, r;
	k = chessboard.at(4);
	r = chessboard.at(0);
	make_move(k,k.pos-2);
	make_move(r,r.pos+3);}

bool test_for_check() { 
	for ( auto p : active_pieces ) {
		if (check_from(p)) return true;}
	return false;}

void swap_sides() {
	status.white = !status.white;
	update_piece_list();}

bool is_king_in_check(piece p, int m) {
	bool result;
	piece store;
	store = make_move(p, m);
	swap_sides();
	result = test_for_check(); 
	undo_move(p,store);
	swap_sides();
	return result;}

void init_piece_value() {
	piece_value['.'] =       0;
	piece_value['p'] =    -100;
	piece_value['b'] =    -300;
	piece_value['n'] =    -300;
	piece_value['r'] =    -500;
	piece_value['q'] =    -900;
	piece_value['k'] =  -20000;
	piece_value['P'] =     100;
	piece_value['B'] =     300;
	piece_value['N'] =     300;
	piece_value['R'] =     500;
	piece_value['Q'] =     900;
	piece_value['K'] =   20000;}

int evaluate() {
	int score = 0;
	int factor = 1;
	if (!status.white) factor = -1;
	for(auto el : chessboard) {
	  	score += el.value;
		if (el.type == 'n' or el.type =='N'){
		  score += factor * knight_evaluation.at(el.pos);}
		if (el.type == 'p') {
			score += factor * pawn_evaluation_black.at(el.pos);}
		if (el.type == 'P') {
			score += pawn_evaluation_white.at(el.pos);}}
	if (status.white) score = -score;
	return score;}

int evaluate_simple_material() {
	int score = 0; 
	for(auto el : chessboard){
		score += el.value;}
	if (status.white) score = -score;
	return score;} 

void test_evaluate() {
	/* Testing Playground */
	float starttime, endtime;
	init_chessboard();
	static bool test;
	starttime = (float) clock()/CLOCKS_PER_SEC;
	for (int i = 1; i < 100000000; i++){
	for (int j = 0; j <  64 ; j++) {
		test = ((chessboard.at(j).value) > 0);}}
	endtime = (float) clock()/CLOCKS_PER_SEC;
	std::cout << test;
	std::cout << std::to_string(endtime-starttime) << std::endl;}

int alpha_beta (int alpha, int beta, int depth) {
	if(depth == 0) { 
		return evaluate();}
	int  score;
	piece store;
	std::vector<piece> pieces_store;
	swap_sides();
	for (auto p : active_pieces) {
		for (auto m : legal_moves(p)) {
			if (not is_king_in_check(p, m)) {
				pieces_store = active_pieces;
				store = make_move(p, m);
				score = -alpha_beta(-beta, -alpha, depth-1); 
				undo_move(p, store);
				active_pieces = pieces_store;
				if (score >= beta){
					swap_sides();
					return beta;}
				if (score > alpha){
					alpha = score;}}}}
	swap_sides();
	return alpha;} 

scored_move search_move(scored_move v) {
	int depth = 4; 
	bool iterative_deepening = false;
	std::vector<scored_move> very_best_moves;
	std::vector<scored_move> some_moves;
	std::vector<scored_move> lesser_moves;
	std::vector<piece> pieces;
	piece store;
	pieces = active_pieces;
	int max =   -1000000;
	int alpha = -1000000;
	int beta =   1000000;
	int score = -1000000;
	for ( auto p : pieces ){
		for (auto m : legal_moves(p)) {
			if (not is_king_in_check(p, m)) {
				store = make_move(p,m);
				if (iterative_deepening){
					score = -alpha_beta(-beta, -alpha, 3);}
				else {
					score = -alpha_beta(-beta, -alpha,depth);}
				undo_move(p,store);
				if (score >= max) { 
					max = score;
					some_moves.push_back({score,p, to_move(m)});}
				else if (iterative_deepening) {
					lesser_moves.push_back({score,p, to_move(m)});}}}}
	if (iterative_deepening){
		lesser_moves.insert(lesser_moves.end(),some_moves.begin(),some_moves.end());
		alpha = -1000000;
		beta =   1000000;
		max =   -1000000;
		some_moves.clear();
		very_best_moves.clear();
		std::reverse(lesser_moves.begin(),lesser_moves.end());
		for (auto ve : lesser_moves){
			if (not is_king_in_check(ve.p, pos(ve.m))) {
				store = make_move(ve.p, pos(ve.m));
				score = -alpha_beta(-beta,-alpha,depth);
				undo_move(ve.p,store);
				if (score >= max){
					max = score;
				        some_moves.push_back({score,ve.p,ve.m});}}}}
	if (castling_possible() and not computer_castling.already_castled) {
		piece k = chessboard.at(4);
		if (not is_king_in_check(k,k.pos) and
		    not is_king_in_check(k,k.pos+1) and
		    not is_king_in_check(k,{k.pos+2}))  { 
			computer_castling.already_castled = true;
			make_castling_move();
			update_piece_list();
			v.p.type = 'k';
			v.p.x = 4;
			v.p.y = 8; 
			v.m.x = 6;
			v.m.y = 8;
			return {score, v.p, v.m};}}
	if (castling_queenside_possible() and not computer_castling.already_castled) {
		piece k = chessboard.at(4);
		if (not is_king_in_check(k, k.pos) and
		    not is_king_in_check(k, k.pos-1) and
		    not is_king_in_check(k, k.pos-2))  { 
			computer_castling.already_castled = true;
			make_castling_queenside_move();
			update_piece_list();
			v.p.type = 'k';
			v.p.x = 4;
			v.p.y = 8;
			v.m.x = 2;
			v.m.y = 8;
			return {score, v.p, v.m};}}
	for (auto el : some_moves) {
		if (el.score == max) {very_best_moves.push_back(el);}}
	move_log("BestMovesSize:",std::to_string(very_best_moves.size()));
 	if (!very_best_moves.empty()){
		v = very_best_moves.at(random(very_best_moves.size()));}
	else {std::cout << "1-0 {White mates}" << std::endl;}
	move_log("FinalScore:", std::to_string(max));
	make_move(v.p,pos(v.m));
	update_piece_list();
	bookkeeper();
	return (v);}
					
std::string get_move() {
	float starttime, endtime;
	scored_move v;
	starttime = (float) clock()/CLOCKS_PER_SEC;
	v = search_move(v);
	endtime = (float) clock()/CLOCKS_PER_SEC;
	move_log("Elapsed Time: ",std::to_string(endtime-starttime));
	std::stringstream mov;
	char col1 = 'a' + v.p.x;
	char col2 = 'a' + v.m.x;
	std::string row1 = std::to_string(v.p.y);
	std::string row2 = std::to_string(v.m.y);
	mov << "move " << col1 << row1 << col2 << row2;
	return mov.str();}

void init_engine() {
	init_chessboard();
	init_piece_value();
	update_piece_list();}
